/* ========================================================================= */
/* ------------------------------------------------------------------------- */
/*!
  \file			tree3d.cc
  \date			Dec 2011
  \author		TNick

  \brief		Contains the implementation for Tree3D class


*//*

 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Please read COPYING and README files in root folder
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

*/
/* ------------------------------------------------------------------------- */
/* ========================================================================= */
//
//
//
//
/*  INCLUDES    ------------------------------------------------------------ */

#include	<QDebug>

#include	<objdeflib_internal.h>


#include	"tree3d.h"


/*  INCLUDES    ============================================================ */
//
//
//
//
/*  DEFINITIONS    --------------------------------------------------------- */



/*  DEFINITIONS    ========================================================= */
//
//
//
//
/*  DATA    ---------------------------------------------------------------- */

/*  DATA    ================================================================ */
//
//
//
//
/*  CLASS    --------------------------------------------------------------- */


/* ------------------------------------------------------------------------- */
int						Tree3D::index				( void ) const
{
	int i = -1;
	const Tree3D * itr = this;
	while ( itr != NULL )
	{
		itr = itr->prev_;
		i++;
	}
	return i;
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3D::insAfter			( Tree3D * new_node )
{
	new_node->next_ = next_;
	new_node->prev_ = this;
	if (next_ != NULL)
	{ /* not last item */
		new_node->next_->prev_ = new_node;
	}
	next_ = new_node;

}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3D::insBefore			( Tree3D * new_node )
{
	new_node->next_ = this;
	new_node->prev_ = prev_;
	if (prev_ != NULL)
	{ /* not first item */
		prev_->next_ = new_node;
	}
	prev_ = new_node;

}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3D::extract				( void )
{
	if (next_ != NULL)
	{
		next_->prev_ = prev_;
	}
	if (prev_ != NULL)
	{
		prev_->next_ = next_;
	}
	prev_ = NULL;
	next_ = NULL;
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3D::dbgDump				( void ) const
{
	qDebug() << this
			 << " father: " << father()
			 << " prev: " << previous()
			 << " next: " << next();
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
Tree3D*					Tree3DNode::kid				( int nth ) const
{
	int i = 0;
	Tree3D *	iter = kid1_;
	while ( iter != NULL )
	{
		if ( i == nth )	return iter;
		iter = iter->next();
		i++;
	}
	return NULL;
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
int						Tree3DNode::count			( void ) const
{
	int i = 0;
	const Tree3D *	iter = kid1_;
	while ( iter != NULL )
	{
		iter = iter->next();
		i++;
	}
	return i;
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3DNode::dbgDump			( void ) const
{
	qDebug() << this
			 << " father: " << father()
			 << " prev: " << previous()
			 << " next: " << next()
			 << " kid 1: " << firstKid();
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3DNode::append			( Tree3D * it_leaf )
{
	Tree3D *	iter = kid1_;
	if ( iter == NULL )
	{
		kid1_ = it_leaf;
		it_leaf->setNext( NULL );
		it_leaf->setPrevious( NULL );
		return;
	}

	while ( iter->next() != NULL )
	{
		iter = iter->next();
	}
	iter->setNext( it_leaf );
	it_leaf->setPrevious( iter );
	it_leaf->setNext( NULL );

}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
void					Tree3DNode::prepend			( Tree3D * it_leaf )
{
	Tree3D *	iter = kid1_;
	if ( iter == NULL )
	{
		kid1_ = it_leaf;
		it_leaf->setNext( NULL );
		it_leaf->setPrevious( NULL );
		return;
	}

	iter->setPrevious( it_leaf );
	it_leaf->setPrevious( NULL );
	it_leaf->setNext( iter );
	kid1_ = it_leaf;

}
/* ------------------------------------------------------------------------- */

/* ========================================================================= */
void					Tree3DNode::clear			( void )
{
	Tree3D *		iter = kid1_;
	Tree3D *		tmp;
	while ( iter != NULL )
	{
		tmp = iter->next();
		if ( iter->isNode() )
		{
			static_cast<Tree3DNode *>( iter )->clear();
		}
		delete iter;
		iter = tmp;
	}
}
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
Tree3D*					Tree3DNode::lastKid			( void ) const
{
	Tree3D *	iter = kid1_;
	if ( iter == NULL )
	{
		return NULL;
	}
	while ( iter->next() != NULL )
	{
		iter = iter->next();
	}
	return 	iter;
}
/* ========================================================================= */


#ifdef	OBJECTSLIB_TESTS

/* ------------------------------------------------------------------------- */
void				Tree3D_Tests					(
		int & performed, int & succeded )
{
	QString		Outcm;
	performed = 0;
	succeded = 0;
	bool		b_ok;


	Tree3D * l1 = new Tree3D;
	for (;;)	{

		if ( l1->isNode() == true ) break;
		if ( l1->next() != NULL ) break;
		if ( l1->previous() != NULL ) break;
		if ( l1->father() != NULL ) break;
		if ( l1->index() != 0 ) break;

		b_ok = true; break;
	}
	TEST_RESULT( b_ok, "Basic Tree3D" );

	Tree3DNode * n1 = new Tree3DNode;
	for (;;)	{

		if ( n1->isNode() == false ) break;
		if ( n1->next() != NULL ) break;
		if ( n1->previous() != NULL ) break;
		if ( n1->father() != NULL ) break;
		if ( n1->index() != 0 ) break;

		if ( n1->firstKid() != NULL ) break;
		if ( n1->lastKid() != NULL ) break;
		if ( n1->kid( 0 ) != NULL ) break;
		if ( n1->kid( -1 ) != NULL ) break;
		if ( n1->kid( 1 ) != NULL ) break;

		if ( n1->count( ) != 0 ) break;

		b_ok = true; break;
	}
	TEST_RESULT( b_ok, "Basic Tree3DNode" );


	n1->append( l1 );
	for (;;)	{

		if ( n1->isNode() == false ) break;
		if ( n1->next() != NULL ) break;
		if ( n1->previous() != NULL ) break;
		if ( n1->father() != NULL ) break;
		if ( n1->index() != 0 ) break;

		if ( n1->firstKid() != l1 ) break;
		if ( n1->lastKid() != l1 ) break;
		if ( n1->kid( 0 ) != l1 ) break;
		if ( n1->kid( -1 ) != NULL ) break;
		if ( n1->kid( 1 ) != NULL ) break;

		if ( n1->count( ) != 1 ) break;

		b_ok = true; break;
	}
	TEST_RESULT( b_ok, "Tree3DNode with a kid" );

	Tree3D * l0 = new Tree3D;
	Tree3D * l2 = new Tree3D;
	Tree3D * l3 = new Tree3D;

	n1->prepend( l0 );
	n1->append( l2 );
	n1->append( l3 );
	for (;;)	{

		if ( n1->isNode() == false ) break;
		if ( n1->next() != NULL ) break;
		if ( n1->previous() != NULL ) break;
		if ( n1->father() != NULL ) break;
		if ( n1->index() != 0 ) break;

		if ( n1->firstKid() != l0 ) break;
		if ( n1->lastKid() != l3 ) break;
		if ( n1->kid( 0 ) != l0 ) break;
		if ( n1->kid( 1 ) != l1 ) break;
		if ( n1->kid( 2 ) != l2 ) break;
		if ( n1->kid( 3 ) != l3 ) break;
		if ( n1->kid( -1 ) != NULL ) break;

		if ( n1->count( ) != 4 ) break;


		if ( l0->isNode() == true ) break;
		if ( l0->next() != l1 ) break;
		if ( l0->previous() != NULL ) break;
		if ( l0->father() != n1 ) break;
		if ( l0->index() != 0 ) break;

		if ( l1->isNode() == true ) break;
		if ( l1->next() != l2 ) break;
		if ( l1->previous() != l0 ) break;
		if ( l1->father() != n1 ) break;
		if ( l1->index() != 1 ) break;

		if ( l2->isNode() == true ) break;
		if ( l2->next() != l3 ) break;
		if ( l2->previous() != l1 ) break;
		if ( l2->father() != n1 ) break;
		if ( l2->index() != 2 ) break;

		if ( l3->isNode() == true ) break;
		if ( l3->next() != NULL ) break;
		if ( l3->previous() != l2 ) break;
		if ( l3->father() != n1 ) break;
		if ( l3->index() != 3 ) break;


		b_ok = true; break;
	}
	TEST_RESULT( b_ok, "Tree3DNode with 4 kids" );

	n1->clear();
	/*
	delete n1;
	delete l0;
	delete l1;
	delete l2;
	delete l3;
	*/
	for (;;)	{

		if ( n1->isNode() == false ) break;
		if ( n1->next() != NULL ) break;
		if ( n1->previous() != NULL ) break;
		if ( n1->father() != NULL ) break;
		if ( n1->index() != 0 ) break;

		if ( n1->firstKid() != NULL ) break;
		if ( n1->lastKid() != NULL ) break;
		if ( n1->kid( 0 ) != NULL ) break;
		if ( n1->kid( -1 ) != NULL ) break;
		if ( n1->kid( 1 ) != NULL ) break;

		if ( n1->count( ) != 0 ) break;

		b_ok = true; break;
	}
	TEST_RESULT( b_ok, "Tree3DNode after clear" );


	Tree3D * crtl;
	Tree3D * prev_l;
	Tree3DNode * crtn;
	int i; int j; int test_sz = 100;

	for ( i = 0; i < test_sz; i++)
	{
		crtn = new Tree3DNode( );
		n1->append( crtn );
		for ( j = 0; j < test_sz; j++ )
		{
			crtl = new Tree3D( );
			crtn->append( crtl );
		}
	}

	for ( i = 0; i < test_sz; i++)
	{
		crtn = static_cast<Tree3DNode*>( n1->kid( i ) );
		prev_l = NULL;
		if ( crtn == NULL ) break;
		if ( crtn->isNode() == false ) break;
		if ( n1->father() != n1 ) break;
		if ( n1->index() != i ) break;

		for ( j = 0; j < test_sz; j++ )
		{
			crtl = crtn->kid( j );
			if ( crtl == NULL ) break;
			if ( crtl->isNode() == true ) break;
			if ( crtl->previous() != prev_l ) break;
			if ( n1->father() != crtn ) break;
			if ( n1->index() != j ) break;
			prev_l = crtl;
		}
		if ( j != test_sz ) break;
	}
	TEST_RESULT( i != test_sz, "3 level tree" );

	n1->clear();

}
/* ========================================================================= */

#endif

/*  CLASS    =============================================================== */
//
//
//
//
/* ------------------------------------------------------------------------- */
/* ========================================================================= */
